public class HasCycle {
    public static boolean hasCycle(MySingleList.ListNode head) {
        //利用快慢双指针法，快指针每次走两步，慢指针每次走一步，如果链表存在环的话，慢指针会被快指针套圈，即快慢指针将会相遇
        MySingleList.ListNode fast = head;
        MySingleList.ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    public static void main1(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(3);
        list.addLast(2);
        list.addLast(0);
        list.addLast(4);

        MySingleList.ListNode cur = list.head;
        //寻找最后一个结点
        while(cur.next != null) {
            cur = cur.next;
        }

        MySingleList.ListNode last = cur;
        cur = list.head;
        //在链表中建立环
        while(cur.val != 2) {
            cur = cur.next;
        }

        last.next = cur;


        boolean result = hasCycle(list.head);
        System.out.println(result);

    }

    public static void main2(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);

        MySingleList.ListNode cur = list.head;
        while(cur.next != null) {
            cur = cur.next;
        }

        MySingleList.ListNode last = cur;
        cur = list.head;

        while(cur.val != 2) {
            cur = cur.next;
        }

        last.next = cur;

        boolean result = hasCycle(list.head);
        System.out.println(result);
    }

    public static void main3(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(1);

        boolean result = hasCycle(list.head);
        System.out.println(result);
    }
}
